package com.some;

public class SubArrayEqual {
 
    static int testShare(int[]a,int n,int m,int sum,int groupSum,int[] aux,int goal,int groupId ){
        if(goal<0){
            return 0;
        }
 
        if(goal==0){
            groupId ++;
            goal = groupSum;
            if(groupId == m+1){
                return 1;
            }
        }
        for(int i=0;i<n;i++){
            if(aux[i]!=0)
                continue;
            aux[i] = groupId;
            if(testShare(a,n,m,sum,groupSum,aux,goal-a[i],groupId)!=0)
                return 1;
            //如果不合适把该元素置为可用
            aux[i] = 0 ;
        }
        return 0;
    }
 
    static int maxShare(int[] a,int n){
        int sum = 0;
 
        int[] aux = new int[n];
 
        for(int i=0;i<n;i++) sum+=a[i];
 
        for(int m=n;m>=2;m--){
            if(sum%m!=0) continue;
            for(int i=0;i<n;i++){
                aux[i] =0;
            }
            if(testShare(a,n,m,sum,sum/m,aux,sum/m,1)!=0){
                System.out.println("分组情况：");
                for(int i=0;i<n;i++){
                    System.out.print(aux[i]);
                }
                System.out.println();
                System.out.println("------------");
                aux = null;
                return m;
            }
        }
        return 1;
    }
 
    public static void main(String[] args) {
        int a[] = {3,2,4,3,6};
        System.out.println(maxShare(a,a.length));
    }
}